A computer network includes computer processors or “hosts” that host software applications that provide or request services, or both. The hosts may be network terminals or end stations that do not perform network traffic routing or forwarding functions. The hosts communicate with each other through network devices, such as switches and routers, sometimes called intermediate devices, which do perform routing and forwarding functions. When a host is added to a network by connecting directly to another host, or indirectly to another host through one or more intermediate devices, the host must be configured for network operations. For example, the newly added host is assigned a logical network address for itself, and a network address for the intermediate device that routes or forwards its traffic, among other configuration information.
Computer networks that employ the Transmission Control Protocol and Internet Protocol (TCP/IP) for sending packets of information between devices on the network are proliferating, and as a result, logical network addresses that are used to locate each device on the network have become scarce. Further, in many local networks with many different computers, the number and location of the computers connected to the network may change regularly. In addition, of the many computers physically connected at one time, only a fraction of the computers are on and operating at one time. Thus one or more hosts are being added and dropped frequently.
A specific context in which this problem arises involves large-scale cable modem networks in which voice and other services are delivered over an Internet Protocol network that uses coaxial cable for communications. Addresses are dynamically assigned to cable modems of end users as the users subscribe to and terminate use of service, and to devices that cannot persistently store an address. In this context, it is wasteful to give every device a unique and permanent network address. A number of addresses sufficient for the total anticipated subscriber base can be shared, but configuring each host with a new address is a tedious process to perform manually.
The Dynamic Host Configuration Protocol (DHCP) provides a mechanism through which computers using TCP/IP can obtain network addresses and other configuration information automatically. DHCP is an open standard protocol for dynamic host configuration described in request for comments (RFC) documents numbered 2131 and 2132 available at the time of this writing as rfc2131.txt and rfc2132.txt, respectively, on the worldwide web (www) at domain and directory ietf.org/rfc. A DHCP server process operates on a DHCP server host that is conveniently located for several hosts on one or more local networks. One or more DHCP server hosts and processes are set up by a system administrator with information to configure the hosts on one or more local networks to reflect the current architecture of those local networks. A DHCP client process operates on each host of the local networks. As used hereinafter, a server refers to the server process and a client refers to the client process unless otherwise indicated to refer to the host or device on which the process executes.
Multiple DHCP servers may serve the same network or portion of the network. The IP addresses available for each network or portion of the network are distributed among the DHCP servers and placed in a data structure at each DHCP, thus forming a pool of addresses that the individual DHCP server may allocate. In conventional systems, a network administrator divides a set or range of network addresses among multiple DHCP servers to reflect the current architecture of the network. Many thousands and even millions of network addresses might be stored in the address pools of the multiple DHCP servers. It is an extremely tedious and error-prone process to manually apportion thousands of network addresses among the address pools of dozens or hundreds of DHCP servers.
One approach to simplify the manual process is to specify a set of contiguous network addresses for a DHCP server as a subnet. A subnet is a base address and a range of addresses above the base address, and therefore is simpler to enter manually as compared to listing each address individually. An IP address consists of 32 bits, often represented as four 8-bit numbers separated by periods, e.g., A.B.C.D, where the letters A, B, C, D each represent one 8-bit number. An 8-bit number can represent values from 0 though 255. In a range of contiguous addresses the leftmost bits are constant and the rightmost change. For example, in a range of network addresses from 20.17.123.000 to 20.17.123.255 the three 8-bit numbers on the left are constant, i.e., the 24 leftmost bits are constant. Network hosts use their knowledge of the subnet that their address is part of when they send messages. Messages that are destined for another host on the same subnet can usually be sent directly to that host. Messages destined for hosts on different subnets usually need to be forwarded to that other subnet by a router. A virtual mask is laid over an address in order to separate it into the leftmost, or network part, and the rightmost, or host part. Routers may use the network portion of the address to efficiently direct traffic to physical segments of the network.
The number of bits in the mask is the size of the mask. The size of the mask is an indicator of the range in the subnet because the remaining bits are allowed to change within the subnet. For example, the mask of size 24 bits implies a range of 8 bits, from 0-255, for addresses in the subnet. The subnet always begins at an address with all zeroes in the unmasked portion.
Several problems occur even with specifying addresses in subnets. First, the apportionment among multiple DHCP servers is still manual, and therefore tedious and error-prone where there are many DHCP servers and many subnets. Second, even if values are entered correctly, the apportionment may not be optimal for the actual distribution of hosts on the network. One DHCP server may be apportioned too large a subnet or too many subnets for the number of hosts that use the portion of the network the DHCP server serves, while another DHCP server may be apportioned too small or too few subnets. When a shortage of addresses arises at one DHCP server, the network administrator manually identifies a DHCP server with excess addresses and moves at least some of the excess addresses, perhaps in one or more subnets, to the DHCP server experiencing a shortage. Alternatively the network administrator manually requests additional subnets from a higher authority.
In one approach, a dynamic subnet configuration server (DSC server) is introduced to assign subnets to DHCP servers as requested by the DHCP servers. However, this does not eliminate the problems of conventional DHCP servers, and an administrator must still apportion subnets among the DSC servers if there are multiple DSC servers. Also, a DSC server cannot automatically request additional subnets when all its subnets have been assigned.
Another problem is that the DSC server does not consider the relative needs of DHCP servers requesting the subnets. For example, two DHCP servers may request renewal of their subnets of mask size 24 bits, yet one of the requesting DHCP servers may be using 45% of the addresses in the subnets while the other is using 90%. If network addresses are scarce, it is more desirable to apportion a smaller subnet (i.e., a subnet having a larger mask size) to the first DHCP server than to the second. For example, it is desirable to renew the DHCP server that is making 45% use of its addresses with a subnet of mask size 25 while providing the full subnet of mask size 24 to the DHCP server making use of 90% of its addresses.
In an approach presented in Johnson et al., modified DHCP servers behave as subnet management processes to manage and distribute subnets of addresses among themselves in addition to leasing individual network addresses to hosts. As described in Johnson et al., multiple modified DHCP servers communicate using DHCP messages to automatically apportion subnets among each other based on the relative usage of the subnets. In addition, an individual router may request a subnet for use on its particular network segment.
However, the approach presented in Johnson et al., does not disclose details about how a particular subnet management process selects a particular subnet from one or more subnets of available network addresses to satisfy a request from another subnet management process.
One past approach is to divide the pool of network addresses managed by the subnet management process into multiple subnets of the same fixed or specified size. The specified size is selected to satisfy the typical request for a subnet. For example, the specified size is selected to have a mask size of 25 so that each subnet includes 128 addresses. As each request to lease a subnet arrives at the subnet management process, the subnet management process allocates the next available subnet. When a lease expires or a requesting process releases a subnet, the subnet is made available for the next requesting process.
However, while suitable for many purposes, this approach has numerous disadvantages. One disadvantage is that the specified size may be too large for some requests, which is wasteful of scarce network address space. For example, the subnet request may be for a process operating on a router serving as the only intermediate device connected to a segment with four hosts. If there are no further segments down this path, allocating a subnet with 128 addresses to such a router wastes 123 addresses that might be needed on a different set of network devices.
Another disadvantage is that the specified size may be too small for some requests, which causes the response to waste network bandwidth. For example, a request from another subnet management process for a subnet of 1024 addresses to allocate to a heavily used network would require the supplying subnet management process to send eight subnets of 128 addresses each. Sending eight subnets takes eight times the data needed to send one subnet. Therefore more data is sent and more bandwidth is consumed.
Furthermore, in some cases, only one subnet is sent in response to each request, so the request for 1024 addresses would be repeated eight times to obtain the eight responses; consequently eight times the network traffic is produced. This approach consumes even more network bandwidth than including eight subnets in one response because the other fields of the TCP/IP and DHCP protocols are repeated in each of the eight responses, and seven additional requests are made.
Another disadvantage is that multiple discontinuous subnets may be allocated to the same intermediate device. Multiple discontinuous segments assigned to segments connected to the same intermediate device may complicate the routing mechanism employed on the intermediate device and intervening intermediate devices. For example, assume that four subnets of a mask size of 27 and starting addresses A.B.C.0, A.B.D.64 and A.B.E.32 and A.B.E.128 are delegated to a requesting subnet management process that allocates addresses on a given portion of the network behind a certain router. Intervening intermediate devices require four separate entries in their routing tables for the four subnets that direct traffic to that certain router. In general, this is less efficient, at each intermediate device, than having a single entry in the routing tables for all the hosts connected through the same router. Thus, it would be preferable for the four subnets of mask size 27 delegated by the subnet management process to be adjacent, so that they can be represented in routing tables by a single subnet of mask size 25. For example, it would be preferable for the 128 addresses to be represented by a single subnet of mask size 25 and starting address A.B.E.128. Then the intermediate devices between the sending host and that certain router can direct all traffic to that router based on a single entry in the routing tables.
The details of how a particular subnet is constructed or selected from the available network addresses should be chosen in a way that is appropriate for particular network architecture. Different approaches are appropriate for different network architectures. For example, network architectures in which all the subnet management processes are serving portions of the network that are similar in size may be well served by a plurality of subnets of a certain size. However, in networks in which address space is extremely scarce, it may be preferable to provide subnets no larger than the size requested or used. While, in networks in which there are many intermediate devices with complex routing computations that affect throughput, adjacent subnets should be assigned to a particular device requesting multiple subnets. Other network architectures may benefit from other policies for selecting available subnets developed by users of the other network architectures.
Based on the foregoing, there is a clear need for techniques that permit the use of one or more policies for selecting subnets of available addresses from a plurality of network addresses managed by a subnet management process.
In particular, there is a need for a policy for selecting subnets that minimizes waste of scarce network address space.
In particular, there is a need for a policy for selecting subnets that reduces complexity in routing traffic to hosts using addresses from those subnets.
There is also a need for techniques that allow a user to employ a particular policy for selecting available subnets that is appropriate for a user's particular network architecture.